مسئله خواننده-نویسنده

در علوم کامپیوتر مسئله‌های خواننده‌ها- نویسنده‌ها مثال‌هایی از یک مشکل محاسباتی شایع در بحث همروندی هستند. حداقل سه نوع مسئله در این رابطه وجود دارد که با شرایطی در ارتباط است که در آن چندین ریسۀ در حال اجرا به‌طور همزمان سعی می‌کنند تا در یک لحظه به منبع مشترکی دست پیدا کنند. برخی ریسه‌ها ممکن است بخوانند و برخی دیگر ممکن است بنویسند، با این محدودیت که هیچ ریسه‌ای در حالی‌که ریسه دیگری در حال نوشتن در منبع مشترک است، امکان دسترسی به منبع مشترک را چه برای خواندن و چه برای نوشتن نداشته باشد. به‌طور خاص، ما می‌خواهیم تا مانع از این شویم که بیش از یک ریسه به‌طور همزمان منبع مشترک را تغییر ندهند و دو یا بیش از دو خواننده اجازه دسترسی به منبع مشترک را به‌صورت همزمان داشته باشند. یک قفل خواننده‌ها-نویسنده نوعی ساختمان داده‌ای است که یک یا بیش از یک مسئله خواننده‌ها-نویسنده‌ها را حل می‌کند.

اولین مسئله خواننده و نویسنده‌ها

فرض کنید که ما یک ناحیه مشترک حافظه (ناحیه بحرانی) با محدودیت‌های اساسی ذکر شده در بالا داریم. این امکان وجود دارد تا داده مشترک را در پشت یک انحصار متقابل، mutex، حفاظت کنیم. در این حالت دو ریسه به‌طور همزمان نمی‌توانند به داده دسترسی پیدا کنند. با این حال، این راه حل بهترین راه حل نیست؛ زیرا این امکان وجود دارد که یک خواننده مثلاً با نام R1 قفل را داشته باشد و سپس خوانندهٔ دیگری مثلاً با نام R2 درخواست دسترسی کند. منطقی نیست که R2 منتظر بماند تا R1 کارش تمام شود و سپس عملیات خواندن را شروع کند، در عوض، R2 باید این اجازه را داشته باشد که همزمان با R1 منبع را بخواند؛ زیرا عملیات خواندن موجب تغییر داده نمی‌شود؛ بنابراین خواندن‌های همزمان بی خطر هستند. این شرایط انگیزه‌ای برای حل اولین مشکل خواننده ها- نویسنده‌ها هست که در آن محدودیت‌هایی اضافه می‌شود که اگر منبع مشترک در حال حاضر برای خواندن باز باشد، هیچ خواننده ای نباید منتظر بماند. به این راه حل، اولویت خواننده‌ها می‌گویند و کد آن در زیر نشان داده شده‌است:

semaphore resource=1;
semaphore rmutex=1;
readcount=0;
 resource.P() is equivalent to wait(resource)
 resource.V() is equivalent to signal(resource)
 rmutex.P() is equivalent to wait(rmutex)
 rmutex.V() is equivalent to signal(rmutex)
*/

writer() {
 resource.P();          //Lock the shared file for a writer

 <CRITICAL Section>
 // Writing is done

 <EXIT Section>
 resource.V();          //Release the shared file for use by other readers. Writers are allowed if there are no readers requesting it.
}

reader() {
 rmutex.P();           //Ensure that no other reader can execute the <Entry> section while you are in it
 <CRITICAL Section>
 readcount++;          //Indicate that you are a reader trying to enter the Critical Section
 if (readcount == 1)   //Checks if you are the first reader trying to enter CS
 resource.P();     //If you are the first reader, lock the resource from writers. Resource stays reserved for subsequent readers
 <EXIT CRITICAL Section>
 rmutex.V();           //Release

 // Do the Reading

 rmutex.P();           //Ensure that no other reader can execute the <Exit> section while you are in it
 <CRITICAL Section>
 readcount--;          //Indicate that you are no longer needing the shared resource. One fewer reader
 if (readcount == 0)   //Checks if you are the last (only) reader who is reading the shared file
 resource.V();     //If you are last reader, then you can unlock the resource. This makes it available to writers.
 <EXIT CRITICAL Section>
 rmutex.V();           //Release
}

در این راه حل برای مسئله خواننده ها/ نویسنده‌ها، اولین خواننده باید منبع (فایل مشترک) را قفل کند، البته اگر منبعی وجود داشته باشد. زمانی که فایل در برابر نویسنده‌ها قفل شد، خواننده‌های بسیار دیگری، بدون اینکه مجبور باشند قفل آن را مجدداً باز کنند، می‌توانند از آن استفاده کنند.

قبل از ورود به ناحیه بحرانی، هر خوانندهٔ جدید باید از منطقه ورود عبور کند. با این حال، ممکن است در یک لحظه فقط یک خواننده در منطقه ورود وجود داشته باشد. این کار برای این انجام می‌شود تا شرایط رقابتی بین خواننده‌ها به وجود نیاید (در این بستر، شرایط رقابتی شرایطی است که در آن دو یا بیش از دو ریسه به‌طور همزمان از خواب بیدار می‌شوند و تلاش می‌کنند تا وارد بخش بحرانی شوند؛ بدون محدودیت‌های بیشتر، این رفتار نامعین است؛ یعنی دو خواننده به صورت همزمان readcount را افزایش می‌دهند و هر دو سعی می‌کنند تا منبع را قفل کنند. این کار موجب می‌شود تا یک خواننده مسدود شود). برای عملی کردن این روش هر خواننده که وارد بخش ورود می‌شود، بخش ورود را برای خودش قفل می‌کند تا زمانی که کارش تمام شود. در طی این زمان، خوانندهٔ مذکور منبع را قفل نمی‌کند، و فقط منطقه ورود را قفل می‌کند تا هیچ خواننده دیگری در حالی که او در داخل آن قرار دارد، نتواند وارد این بخش شود. زمانی که خوانندهٔ مذکور اجرای منطقهٔ شروع را به پایان رساند، با سیگنال دهی به mutex قفل آن را باز می‌کند. سیگنال دهی از طریق ()mutex.V در کد بالا انجام می‌شود. برای بخش خروج نیز وضعیت همین است. در یک لحظه بیش از یک خواننده نمی‌تواند در بخش خروج قرار بگیرد، بنابراین هر خواننده ای قبل از استفاده از بخش خروج باید بخش خروج را در اختیار بگیرد و قفل کند.

زمانی که اولین خواننده در بخش ورود هست، منبع را قفل خواهد کرد. با این کار، هیچ نویسنده‌ای اجازهٔ دسترسی به آن را نخواهد داشت. خواننده‌های بعدی فقط می‌توانند از منبع قفل شده (در برابر نویسنده‌ها) استفاده کنند. خواننده ای که آخر از همه تمام می‌کند (توسط متغیر readcount نشان داده می‌شود) باید قفل منبع را باز کند تا منبع در اختیار نویسندگان قرار بگیرد.

در این روش هر نویسنده‌ای باید به‌طور جداگانه مالکیت منبع را در اختیار بگیرد. این بدان معنا است که تعداد زیادی از خواننده‌های متوالی، بعداً می‌توانند دسترسی تمام نویسنده‌های بالقوه را به منبع قفل کنند و آنها را با قحطی منبع مواجه سازند. علت این پدیده این است که بعد از اینکه اولین خواننده منبع را قفل کرد، هیچ نویسنده ای نمی‌تواند آن را قفل کند، تا زمانی که آزاد شود و فقط توسط آخرین خواننده آزاد خواهد شد. از این رو این راه حل منصفانه نیست.

دومین مسئله خواننده ها-نویسنده ها

راه حل اول بهترین راه حل نبود، زیرا این امکان وجود داشت که یک خواننده مثلاً R1 دارای قفل باشد، یک نویسنده مثلاً W منتظر قفل باشد و سپس یک خواننده مثلاً R2 درخواست دسترسی کند. منصفانه نیست که R2 به طور ناگهانی و قبل از W داخل شود؛ اگر این اتفاق به اندازه کافی رخ دهد، W دچار قطعی منبع خواهد شد. درست این است که W در اسرع وقت شروع شود. این امر انگیزه ای است برای راه حل مسئله دوم خواننده ها- نویسنده ها که در آن این محدودیت افزوده می‌شود که هیچ نویسنده‌ای، زمانی که به صف وارد شد، نباید بیش از حد ضروری منتظر بماند. به این راه حل، ارجحیت نویسندگان نیز گویند. یک راه حل برای سناریوی ارجحیت نویسندگان به شکل زیر است:

int readcount, writecount;                   //(initial value = 0)
semaphore rmutex, wmutex, readTry, resource; //(initial value = 1) 

//READER
reader() {
<ENTRY Section>
  readTry.P();                 //Indicate a reader is trying to enter
  rmutex.P();                  //lock entry section to avoid race condition with other readers
  readcount++;                 //report yourself as a reader
  if (readcount == 1)          //checks if you are first reader
    resource.P();              //if you are first reader, lock  the resource
  rmutex.V();                  //release entry section for other readers
  readTry.V();                 //indicate you are done trying to access the resource 

<CRITICAL Section>
//reading is performed 

<EXIT Section>
  rmutex.P();                  //reserve exit section - avoids race condition with readers
  readcount--;                 //indicate you're leaving
  if (readcount == 0)          //checks if you are last reader leaving
    resource.V();              //if last, you must release the locked resource
  rmutex.V();                  //release exit section for other readers
} 

//WRITER
writer() {
<ENTRY Section>
  wmutex.P();                  //reserve entry section for writers - avoids race conditions
  writecount++;                //report yourself as a writer entering
  if (writecount == 1)         //checks if you're first writer
    readTry.P();               //if you're first, then you must lock the readers out. Prevent them from trying to enter CS
  wmutex.V();                  //release entry section
  resource.P();                //reserve the resource for yourself - prevents other writers from simultaneously editing the shared resource
<CRITICAL Section>
  //writing is performed
  resource.V();                //release file 

<EXIT Section>
  wmutex.P();                  //reserve exit section
  writecount--;                //indicate you're leaving
  if (writecount == 0)         //checks if you're the last writer
    readTry.V();               //if you're last writer, you must unlock the readers. Allows them to try enter CS for reading
  wmutex.V();                  //release exit section
}

در این روش ارجحیت به نویسندگان داده می شود، که با مجبور کردن هر خواننده برای قفل کردن و آزاد کردن سمافور readTry به صورت جداگانه میسر می شود. از سوی دیگر، نویسندگان مجبور نیستند که به طور جداگانه آن را قفل کنند. فقط اولین نویسنده readTry را قفل می کند، سپس تمام نویسنده های بعدی می توانند به سادگی و پس از آزاد شدن منبع توسط نویسنده قبلی از آن استفاده کنند. آخرین نویسنده باید سمافور را آزاد کند تا دروازه برای خواننده‌ها باز شود که بتوانند بخوانند.

اگر سمافور قبلاً توسط یک نویسنده ست شده باشد، هیچ خواننده ای نمی‌تواند درگیر بخش ورود شود. خواننده باید منتظر بماند تا آخرین نویسنده قفل منبع و سمافورهای readTry را باز کند. از سوی دیگر، اگر یک خواننده ی خاص سمافور را قفل کرده باشد، به هرگونه نویسنده ی هم روند بالقوه این علامت را می دهد که یک خواننده در بخش ورود قرار دارد. بنابراین، نویسنده منتظر می ماند تا خواننده readTry آزاد کند و سپس نویسنده بلافاصله آن را برای خودش و برای تمام نویسندگان بعدی قفل میکند. با این وجود، نویسنده قادر نخواهد بود تا زمانی که خواننده کنونی منبع را آزاد نکرده است، به منبع دسترسی پیدا کند و منبع زمانی آزاد می‌شود، که خواننده مذکور کارش با منبع در ناحیه بحرانی تمام شده باشد.

هم نویسنده و هم خواننده در منطقه ورود خود می توانند سمافور منبع را قفل کنند. البته برای انجام این کار، باید ابتدا سمافور readTry را قفل کنند که فقط یکی از آنها در هر لحظه می تواند این کار را انجام دهد. اگر هیچ نویسنده‌ای برای دسترسی به منبع وجود نداشته باشد (شرایطی که توسط وضعیت سمافور readTry به خواننده نشان داده می شود)، آنگاه خواننده‌ها منبع را قفل نخواهند کرد. این کار از این جهت انجام می‌شود تا به یک نویسنده اجازه داده شود تا بلافاصله و به محض اینکه خواننده کنونی خواندن را تمام کرد، کنترل منبع را به دست گیرد. در غیر این صورت، نویسنده مجبور خواهد بود تا منتظر صفی از خواننده ها بماند تا کارشان تمام شود و آخرین خواننده بتواند قفل سمافور readTry را باز کند. به محض اینکه یک نویسنده نمایان میشود سعی می‌کند تا readTry را ست کند و در آنجا متوقف می شود و منتظر می ماند تا خواننده کنونی readTry را آزاد کند. سپس، به محض اینکه خواننده کنونی خواندنش تمام شد، کنترل منبع را به دست می گیرد و و مانع از ورود تمام خواننده های بعدی خواهد شد. تمام خواننده های بعدی در سمافور readTry متوقف می شوند و منتظر می مانند تا نویسنده کارش با منبع تمام شود و با آزاد کردن readTry دروازه را باز کند.

اشیاء rmutex و wmutex دقیقاً مشابه با راه حل اول مورد استفاده قرار می‌گیرند. تنها هدف آن ها اجتناب از شرایط مسابقه ای بین خواننده ها و نویسنده ها است، که این شرایط رقابتی در بخش های ورودی یا خروجی آن ها به وجود می آید.

سومین مسئله خواننده ها- نویسنده ها

در حقیقت راه حل هایی که توسط هر دو بیان های مسئله به صورت غیر مستقیم ارائه شد، می تواند منجر به قحطی منبع شود؛ راه حل اول ممکن است نویسنده ها را در صف با قحطی مواجه کند، و راه حل دوم ممکن است خواننده ها را با قحطی مواجه کند. بنابراین مسئله ی سوم خواننده ها- نویسنده ها گاهی مطرح می شود و محدودیت هایی را برقرار می کند که بر پایه آن هیچ ریسه ای نباید گرسنگی بکشد؛ این بدان معنا است که عملیات به دست آوردن یک قفل برای داده مشترک همیشه در یک بازه زمانی محدود شده خاتمه می یابد. یک راه حل که هم برای خواننده ها و هم برای نویسنده ها منصفانه باشد، می تواند به شکل زیر باشد:

int readcount;                // init to 0; number of readers currently accessing resource 

// all semaphores initialised to 1
semaphore resource;           // controls access (read/write) to the resource
semaphore rmutex;             // for syncing changes to shared variable readcount
semaphore serviceQueue;       // FAIRNESS: preserves ordering of requests (signaling must be FIFO) 

//READER
reader() {
<ENTRY Section>
  serviceQueue.P();           // wait in line to be serviced
  rmutex.P();                 // request exclusive access to readcount
  readcount++;                // update count of active readers
  if (readcount == 1)         // if I am the first reader
    resource.P();             // request resource access for readers (writers blocked)
  serviceQueue.V();           // let next in line be serviced
  rmutex.V();                 // release access to readcount
    
<CRITICAL Section>
//reading is performed
    
<EXIT Section>
  rmutex.P();                 // request exclusive access to readcount
  readcount--;                // update count of active readers
  if (readcount == 0)         // if there are no readers left
    resource.V();             // release resource access for all
  rmutex.V();                 // release access to readcount
} 

//WRITER
writer() {
<ENTRY Section>
  serviceQueue.P();           // wait in line to be serviced
  resource.P();               // request exclusive access to resource
  serviceQueue.V();           // let next in line be serviced
    
<CRITICAL Section>
// writing is performed
    
<EXIT Section>
  resource.V();               // release resource access for next reader/writer
}

این راه حل فقط در صورتی می تواند شرایط  "هیچ ریسه ای نباید گرسنگی بکشد" را برآورده کند که سمافور ها در هنگام مسدود کردن و آزاد کردن ریسه ها، ترتیب "اولین ورود- اولین خروج" را حفظ کنند. در غیر این صورت، برای مثال یک نویسنده مسدود شده، در شرایطی که چرخه‌ای از سایر نویسنده ها سمافور را قبل از نویسنده ی مذکور کاهش دهند، ممکن است تا ابد مسدود شده باقی بماند.

ساده ترین مسئله خواننده- نویسنده

ساده ترین مسئله خواننده -نویسنده که فقط از دو سمافور  استفاده میکند و نیازی نیست تا آرایه ای از خواننده ها، داده ی بافر را بخوانند.
دقت کنید که این راه حل به این دلیل ساده تر از مورد کلی است که شبیه مسئله بافر محدود شده است و بنابراین فقط تعداد n خواننده اجازه پیدا می‌کنند که به‌صورت موازی وارد شوند. در اینجا n اندازه بافر است.

الگوریتم

۱. به دلیل سمافور خواندن، خواننده بعد از نویسنده اجرا می شود.

۲. زمانیکه سمافور نوشتن به صفر می رسد، نویسنده نوشتن را متوقف می کند.

۳. زمانیکه سمافور خواندن به صفر می رسد، خواننده خواندن را متوقف می کند.

در نویسنده، مقدار سمافور نوشتن به سمافور خواندن داده می‌شود و در خواننده، مقدار خواندن به نوشتن داده می شود ( در هنگام کامل شدن حلقه ).

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Readers–writers problem». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۱ مارس ۲۰۲۱.